1. Field of the Invention
The present invention generally relates to optimization of industrial processes such as manufacturing, shipping and the like and, more particularly, to prediction of the outcome of detailed optimization processes or sub-problems contained therein characterized by a hierarchical problem sub-structure.
2. Description of the Prior Art
Industrial processes require the utilization of equipment, space, time and other economically valuable resources to achieve their objectives. For example, a manufacturing process may require large and expensive machinery and facilities to manufacture and store a commodity (e.g. paper) in bulk which must be further processed (e.g. cut into desired roll widths and diameters and, often, wound on cores of specified dimensions) to satisfy the specifications of a customer order. Similarly, transportation of a commodity from one or more manufacturing sites to locations required by customers may entail management of a fleet of vehicles covering several different modes of transport which represents a substantial capital and economic expense. These and other industrial and manufacturing processes and services (e.g. utilities. power generation and the like) must be performed at near optimal efficiency if maximum return on investment and profitability is to be obtained.
In a typical optimization problem, there is an objective function which characterizes the quality or xe2x80x9cgoodnessxe2x80x9d of a particular solution (e.g. the qualitative or quantitative degree to which a particular solution meets the objective). There will also be zero or more constraints which must be satisfied for a particular solution to be deemed valid or feasible. The goal of optimization is to identify a feasible solution to a given problem for which the quality of the solution according to the objective function is maximal (or minimal depending on how the objective function is defined). That is, the goal of optimization is to identify the best solution consistent with meeting a set of constraints.
One method that guarantees that an optimal solution will be generated is to exhaustively consider every possible feasible solution using state-space search techniques such as depth-first or breadth-first search. These method will work if 1) there is a well-defined method that guarantees that all feasible solutions can be generated in a finite number of computing steps, and 2) there are sufficient computational resources (time and storage) to allow for this approach. In general, while developing a well-defined methodology is generally not difficult to achieve, provision of sufficient computational resources makes exhaustive search impractical for all but the most simple optimization problems.
In practice, the solving of optimization problems usually includes an attempt to make use of more efficient methods such as linear programming, integer programming, dynamic programming, greedy algorithm heuristics, hill-climbing (also known as means-end analysis) or other heuristic search techniques. Some search methods may also incorporate some degree of randomization in cases where alternative methods tend towards locally optimal but globally sub-optimal solutions. Examples of such techniques are genetic algorithms and simulated annealing. However, there is no guarantee that such techniques will not also suffer from a tendency towards returning locally optimal (but globally sub-optimal) solutions for some problem domains or problem instances within a given domain.
There are also many other limitations to these approaches. For example, a problem can be posed as a linear program only if its constraints and objectives are linear functions. In many difficult problems, the objective function may be highly nonlinear or discontinuous. Some nonlinear optimization problems can be approximated by linear programs if one or more nonlinear components of the problem formulation are left out, or by introducing additional decision variables and constraints to approximate nonlinearities as piece-wise linear functions. Nonlinear objectives may be treated as sub-problems and explored using other aforementioned search techniques.
In summary, practical approaches to complex optimization problems may not guarantee solutions, may require deviation from the preferred characterization of the problem and/or may behave unpredictably. The tendency toward these behaviors increases with the complexity of the optimization problem.
For example, the paper making industry presents some particularly complex problems. When a commercial grade of paper (e.g. other than specialty papers which are sometimes made manually in individual sheets by traditional processes) is initially made, a large, high-capacity machine is used to produce large-width reels, often twenty feet wide or more, the width of which cannot readily be altered. This machine will be capable of producing paper of that width in a number of grades (e.g. newsprint, bond, etc.), weights, finishes and the like from many different compositions of materials (e.g. wood or cloth fiber and mixtures thereof) but only one set of such specifications can be accommodated at any given time.
Therefore, it is advantageous for the manufacturer to fulfill orders with shared product specifications together as part of a batch process in order to avoid the time and material costs associated with altering the specification of the product currently being manufactured. The production of goods having differing specifications must be scheduled including setup time and the time for making transitional product (e.g. having a mixture of constituent compositions between intended compositions) and the risks of other contingencies when specifications are to be changed.
Of course, setups can be readily minimized by combining together all available orders of a common product specification into one batch, but this may not be consistent with satisfying all orders (which may include other product specifications) in a timely fashion. Many other issues pertaining to manufacturing efficiency, profitability, quality and customer satisfaction may influence how manufacturing processes are scheduled.
The paper produced will be formed in a wide continuous sheet of approximately the same width of the web. Some lack of uniformity will occur over a small width at the edges of the wide sheet and the remainder of the width over which the paper quality is uniform is referred to as the xe2x80x9cmaximum decklexe2x80x9d or, simply xe2x80x9cdecklexe2x80x9d, of the machine. This sheet is wound onto a reel and transported to another large machine where it is unrolled, slit into desired widths and again wound onto rolls of desired dimensions which will be specified in the order.
Product specification is not the only criteria by which orders are to be grouped together. In complex manufacturing environments, there are multiple production stages. The manufacturing process employed at one stage may significantly impact the production efficiency at another stage. For example, in the context of paper manufacturing, the widths into which the paper must be cut to conform to orders may involve substantial waste when the total width of all rolls cut from the original reel are less than the total width of the reel itself. Thus, it is not the individual roll widths that determine the relative amount of waste but the combination of widths for particular grades of paper over a plurality of orders, some of which may be only anticipated, along with the ordered or anticipated quantities required for each width.
Further complications may arise since the paper slitting apparatus may not simultaneously accommodate different core sizes or more than a particular number of slitting mechanisms. The production of combinations of narrow rolls which might be expected to more closely match the maximum deckle will increase the number of rolls made from a reel of paper in a given amount of time and may cause bottlenecks in further roll wrapping operations, roll handling operations, and the like. Therefore it can be seen that these constraints on optimization as well as the optimization process, itself, involves many manipulations for allocation of orders to particular machines (assuming two or more machines having differing maximum deckle are available) and run formation and sequencing (RFS) in which the combination of roll widths/sizes to be slit from a sequence of reels is determined.
From the foregoing, it can be readily appreciated that the scheduling of the machinery for manufacture of reels of paper of particular specifications and the scheduling of slitting machinery together with the possibility of maintaining inventory (which is also subject to optimization) presents a highly complex and discontinuous optimization problem. The optimization problem cannot be readily expressed for the general case (e.g. for a realistic set of groups of actual and anticipated orders of variable number and quantity) and potentially presents the problem of returning local rather than global solutions.
Unfortunately, it is often the case that the sub-problems generated by various decompositions are complex optimization problems in their own right and are computationally expensive to solve. Even if a method is known for deriving an optimal solution, the problem instance may be so large as to require impractical levels of computational resources. In these situations, a fast predictor or estimator of the objective value is useful in order to avoid the cost of complete simulation, search, or optimization.
To solve efficiently, many problems can be decomposed into smaller sub-problems. The sub-problems may have the same or different structure. The process of solving the larger xe2x80x9cmasterxe2x80x9d problem becomes one of a) identifying an appropriate partitioning of the master problem into multiple sub-problems, and b) solving each of the sub-problems. In the foregoing discussion, the scheduling of the fulfillment of multiple orders for various products represents the xe2x80x9cMaster problemxe2x80x9d. The partitioning problem is to form and sequence batches of a particular product, determine which orders should be fulfilled as part of each batch. Solving each batch involves scheduling the downstream operations implied by the batch.
In this case, identifying an efficient of slicing the reels produced during this batch implies forming rolls that serve to fulfill the requirements of each order in the batch. The formation of batches may need to be altered if the existing batches lead to downstream inefficiencies. In general, the xe2x80x9cgoodnessxe2x80x9d of the partitioning derived in step (a) may be dependent upon the quality of the sub-problem solutions found in step (b). Thus one must iterate between the master problem and the sub-problems many times until some level of convergence is obtained. That is, each sub-problem is solved or optimized so as to maximize some objective function specific to the particular sub-problem formulation. The solutions to sub-problems are combined to generate an overall solution to the high level optimization problem and the objective value of the sub-problems may be similarly combined to determine the overall objective value of the higher-level optimization problem. This approach is preferred when the sub-problems can be solved in a highly efficient manner. As the sub-problems become more difficult, iteration rapidly become untenable due to finite computational resources.
The inventors have identified the problems of finding an optimal set of sub-problems wherein the measure of correctness of the objective function for these respective sub-problems is, in and of itself, an optimization problem without necessarily requiring solution to the sub-problems and the computational overhead involved in finding optimal solutions for sub-problems which lead to an optimal or near optimal solution for other than the most rudimentary formulations of sub-problems to be a major obstacle to the efficient solution of realistic complex optimization problems. However, no methodology for avoiding the process of solving individual sub-problems or developing an optimal set of such sub-problems in an efficient manner is currently available.
It is therefore an object of the present invention to provide a predictive optimizer to enable optimization of the manner in which a complex optimization problem is decomposed for determination of candidate solutions in such a manner as to employ predictor methods that anticipate the outcome of solution-generating optimization methods as a partial or complete substitute for such solution-generating methods.
It is another object of the invention to provide determination of a solution or a plurality of candidate solutions for a complex optimization problem in reduced time and at reduced computational cost and in which the complex optimization problem is decomposed in a variety of ways.
It is a further object of the invention to provide an increased number of candidate solutions to a complex optimization problem corresponding to a plurality of decompositions and including optimization of the decomposition within the time and computational cost suitable for a scheduling system in an industrial or manufacturing environment.
In order to accomplish these and other objects of the invention, a computer implemented optimization method is provided comprising the steps of decomposing an optimization problem into a first plurality of sub-problems, predicting an evaluation of a solution to a sub-problem, evaluating a composed solution of the optimization problem based on an evaluation of a solution or a predicted evaluation for each sub-problem, and repeating the process using a different decomposition to form a second plurality of sub-problems wherein at least one of the sub-problems of the second plurality of sub-problems differs from sub-problems of the first plurality of sub-problems, preferably in a manner dependent on the predicted quality of optimization of a particular sub-problem.